package com.platform.modules.alg.alglib.poj1195;

public class Poj1195 {
    public String output = "";
    private int maxn = 1050;
    private int c[][];
    private int n;

    int lowbit(int x) {
        return x & (-x);
    }

    // 单点更新
    void add(int x, int y, int z) {
        for (int i = x; i <= n; i += lowbit(i))
            for (int j = y; j <= n; j += lowbit(j))
                c[i][j] += z;
    }

    // 区间和：左上角(1,1)到右下角(x,y)矩阵区间和
    int sum(int x, int y) {
        int s = 0;
        for (int i = x; i > 0; i -= lowbit(i))
            for (int j = y; j > 0; j -= lowbit(j))
                s += c[i][j];
        return s;
    }

    // 求左上角(x1,y1)到右下角(x2,y2)子矩阵区间和
    int sum(int x1, int y1, int x2, int y2) {
        return sum(x2, y2) - sum(x1 - 1, y2) - sum(x2, y1 - 1) + sum(x1 - 1, y1 - 1);
    }

    public String cal(String input) {
        String[] line = input.split("\n");

        int opt, x, y, a, l, b, r, t;
        int i = 0;
        while (true) {
            String[] command = line[i++].split(" ");
            opt = Integer.parseInt(command[0]);
            if (opt == 3) break;
            if (opt == 0) {
                n = Integer.parseInt(command[1]);
                c = new int[maxn][maxn];
            } else if (opt == 1) {
                x = Integer.parseInt(command[1]);
                y = Integer.parseInt(command[2]);
                a = Integer.parseInt(command[3]);
                ++x;
                ++y;
                add(x, y, a);
            } else {
                l = Integer.parseInt(command[1]);
                b = Integer.parseInt(command[2]);
                r = Integer.parseInt(command[3]);
                t = Integer.parseInt(command[4]);
                ++l;
                ++b;
                ++r;
                ++t;
                output += sum(l, b, r, t) + "\n";
            }
        }

        return output;
    }
}
